{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Smallest Subarray Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthSmallestSubarraySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 K 小的子数组和·"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 长度为&nbsp;<code>n</code>&nbsp;的整型数组&nbsp;<code>nums</code>&nbsp;和一个数值&nbsp;<code>k</code>&nbsp;，返回<strong> 第<em>&nbsp;</em><code>k</code>&nbsp;小的子数组和<i>。</i></strong></p>\n",
    "\n",
    "<p><b>子数组</b> 是指数组中一个 <b>非空</b>&nbsp;且不间断的子序列。&nbsp; <b>子数组和</b> 则指子数组中所有元素的和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,1,3], k = 4\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>[2,1,3] 的子数组为：\n",
    "- [2] 和为 2\n",
    "- [1] 和为 1\n",
    "- [3] 和为 3\n",
    "- [2,1] 和为 3\n",
    "- [1,3] 和为 4\n",
    "- [2,1,3] 和为 6 \n",
    "最小子数组和的升序排序为 1, 2, 3, <strong><em>3</em></strong>, 4, 6。 第 4 小的子数组和为 3 。\n",
    "</pre>\n",
    "<strong>示例 2：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3,5,5], k = 7\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>[3,3,5,5] 的子数组为：\n",
    "- [3] 和为 3\n",
    "- [3] 和为 3\n",
    "- [5] 和为 5\n",
    "- [5] 和为 5\n",
    "- [3,3] 和为 6\n",
    "- [3,5] 和为 8\n",
    "- [5,5] 和为 10\n",
    "- [3,3,5], 和为 11\n",
    "- [3,5,5] 和为 13\n",
    "- [3,3,5,5] 和为 16\n",
    "最小子数组和的升序排序为 3, 3, 5, 5, 6, 8, <strong><em>10</em></strong>, 11, 13, 16。第 7 小的子数组和为 10 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n * (n + 1) / 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-smallest-subarray-sum](https://leetcode.cn/problems/kth-smallest-subarray-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-smallest-subarray-sum](https://leetcode.cn/problems/kth-smallest-subarray-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]\\n4', '[3,3,5,5]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 二分查找 + 滑动窗口\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        def countSubarrays(nums, threshold):\n",
    "            count = 0\n",
    "            n = len(nums)\n",
    "            left = 0\n",
    "            sum_val = 0\n",
    "\n",
    "            for right in range(n):\n",
    "                sum_val += nums[right]\n",
    "                while sum_val > threshold:\n",
    "                    sum_val -= nums[left]\n",
    "                    left += 1\n",
    "\n",
    "                count += right - left + 1\n",
    "\n",
    "            return count\n",
    "\n",
    "\n",
    "        min_val = min(nums)\n",
    "        max_val = sum(nums)\n",
    "        low = min_val\n",
    "        high = max_val\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            count = countSubarrays(nums, mid)\n",
    "\n",
    "            if count < k:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        return low\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        max_val = sum(nums)\n",
    "        S = nums[::]\n",
    "        n = len(nums)\n",
    "        for i in range(1,n):\n",
    "            S[i] += S[i-1]\n",
    "\n",
    "        # 双指针统计小于等于val的区间和的个数\n",
    "        def get_less_eq_cnt(val) -> int:\n",
    "            ans = 0\n",
    "\n",
    "            ii, jj = 0, 0\n",
    "            tot = nums[0]\n",
    "            while jj < n:\n",
    "                if nums[jj] > val:\n",
    "                    if jj == n-1:\n",
    "                        break\n",
    "\n",
    "                    ii, jj = jj+1, jj+1\n",
    "                    tot = nums[jj]\n",
    "                    continue\n",
    "\n",
    "                while tot > val:\n",
    "                    tot -= nums[ii]\n",
    "                    ii += 1\n",
    "\n",
    "                ans += jj - ii + 1\n",
    "\n",
    "                if jj == n-1:\n",
    "                    break\n",
    "\n",
    "                tot += nums[jj+1]\n",
    "                jj += 1\n",
    "\n",
    "            return ans\n",
    "\n",
    "        l, r = 1, max_val\n",
    "        ans = None\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            cnt = get_less_eq_cnt(mid)\n",
    "\n",
    "            if cnt >= k:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        def valid(x):\n",
    "            ans = 0\n",
    "            l, r, v = 0, 0, 0\n",
    "            while l < len(nums):\n",
    "                while r < len(nums) and v + nums[r] <= x:\n",
    "                    v += nums[r]\n",
    "                    r += 1\n",
    "                ans += r - l \n",
    "                if ans >= k:\n",
    "                    return True\n",
    "                v -= nums[l]\n",
    "                l += 1\n",
    "            return False \n",
    "        l, r = min(nums), sum(nums)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if valid(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def kthSubarraySum(nums: List[int], k: int) -> int:\n",
    "    \"\"\"第k小的子数组和.k从1开始.\"\"\"\n",
    "    k -= 1\n",
    "    n = len(nums)\n",
    "    preSum = [0] + list(accumulate(nums))\n",
    "\n",
    "    def check(target: int) -> bool:\n",
    "        \"\"\"和小于等于target的子数组个数<=k.\"\"\"\n",
    "        res, left, curSum = 0, 0, 0\n",
    "        for right in range(n):\n",
    "            curSum += nums[right]\n",
    "            while left <= right and curSum > target:\n",
    "                curSum -= nums[left]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res <= k\n",
    "\n",
    "    left, right = 0, preSum[-1]\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "        if check(mid):\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        return kthSubarraySum(nums, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        l,r = min(nums),sum(nums)\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            ll,lr = 0,0\n",
    "            cur = 0\n",
    "            ans = 0\n",
    "            while ll < n:\n",
    "                while lr < n and cur + nums[lr] <= x:\n",
    "                    cur += nums[lr]\n",
    "                    lr += 1\n",
    "                ans += lr - ll\n",
    "                if ll == lr:\n",
    "                   ll += 1\n",
    "                   lr = ll\n",
    "                else:\n",
    "                    cur -= nums[ll]\n",
    "                    ll += 1\n",
    "            return ans >= k\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        acc = [0] + list(accumulate(nums))\n",
    "        def check(lmt):\n",
    "            rnt = 0\n",
    "            for i, x in enumerate(acc):\n",
    "                rnt += bisect_left(acc, x+lmt) - i - 1\n",
    "            return rnt >= k\n",
    "        return bisect_left(range(acc[-1] + 1), True, key=check) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        l = min(nums)\n",
    "        r = sum(nums)\n",
    "\n",
    "        def countSubarrays(n):\n",
    "            left, right = 0, 0  # 初始化窗口的左右边界\n",
    "            count = 0  # 用于记录符合条件的子数组数量\n",
    "            product = 0  # 窗口中元素的乘积\n",
    "\n",
    "            while right < len(nums):\n",
    "                # 扩展右边界并更新窗口内的乘积\n",
    "                product += nums[right]\n",
    "                if product >= n:\n",
    "                    count += len(nums) - right\n",
    "                # 缩小窗口，直到窗口内的乘积小于n\n",
    "                while product >= n and left <= right:\n",
    "                    product -= nums[left]\n",
    "                    left += 1\n",
    "                    if product >=n:\n",
    "                        count += 1\n",
    "\n",
    "                # 扩展右边界\n",
    "                right += 1\n",
    "\n",
    "            return count\n",
    "\n",
    "        def valid(x):\n",
    "            ans = 0\n",
    "            l, r, v = 0, 0, 0\n",
    "            while l < len(nums):\n",
    "                while r < len(nums) and v + nums[r] <= x:\n",
    "                    v += nums[r]\n",
    "                    r += 1\n",
    "                ans += r - l\n",
    "                if ans >= k:\n",
    "                    return True\n",
    "                v -= nums[l]\n",
    "                l += 1\n",
    "            return False\n",
    "\n",
    "\n",
    "        k1 = len(nums) * (len(nums)+1) // 2 - k\n",
    "\n",
    "        while l < r:\n",
    "            if l+1 == r:\n",
    "\n",
    "                if valid(l):\n",
    "                    return l\n",
    "                return r\n",
    "            mid = (l+r)//2\n",
    "\n",
    "            if valid(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "\n",
    "        return -1\n",
    "\n",
    "a = Solution()\n",
    "print(a.kthSmallestSubarraySum(nums = [2,1,3], k = 1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        l=min(nums)\n",
    "        r=sum(nums)\n",
    "        N=len(nums)\n",
    "\n",
    "        def check(mid):\n",
    "            cur=0\n",
    "            c=0\n",
    "            left=0\n",
    "            for i in range(N):\n",
    "                cur+=nums[i]\n",
    "                while cur>mid:\n",
    "                    cur-=nums[left]\n",
    "                    left+=1\n",
    "                c+=i-left+1\n",
    "            return c\n",
    "\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            count=check(mid)\n",
    "            if count<k:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        def check(sm):\n",
    "            l = -1\n",
    "            cur = 0\n",
    "            cnt = 0\n",
    "            for r in range(n):\n",
    "                cur += nums[r]\n",
    "                while cur > sm:\n",
    "                    l += 1\n",
    "                    cur -= nums[l]\n",
    "                cnt += r-l\n",
    "                if cnt >= k:\n",
    "                    return True \n",
    "            return False\n",
    "\n",
    "        total = sum(nums)\n",
    "        l,r = 0, total\n",
    "        while l<=r:\n",
    "            mid = (l+r)>>1\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                res += bisect_right(acc, acc[i] + x) - i - 1\n",
    "            return res >= k \n",
    "        \n",
    "        low, high = 1, acc[-1]\n",
    "        ans = high\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
